#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
vector<int> diStringMatch(string s) {
	int n = s.size();
	vector<int> ret(n + 1);
	if (s[0] == 'I')
		ret[0] = 0, ret[1] = n;
	else
		ret[0] = n, ret[1] = 0;
	int left = 1, right = n - 1;
	for (int i = 1; i < n; i++)
	{
		if (s[i] == 'I')
			ret[i] = right--;
		else
			ret[i] = left++;
	}
	return ret;
}
int findContentChildren(vector<int>& g, vector<int>& s) {
	sort(g.begin(), g.end());
	sort(s.begin(), s.end());
	int gi = 0;
	for (auto& e : s)
	{
		if (e > g[gi]||e==g[gi])
			gi++;
	}
	return gi;
}
string optimalDivision(vector<int>& nums) {
	int n = nums.size();
	if (n == 1)
		return to_string(nums[0]);
	if (n == 2)
		return to_string(nums[0]) + '/' + to_string(nums[1]);
	string ret;
	ret += to_string(nums[0]) + "/(";
	for (int i = 1; i < n; i++)
		ret += to_string(nums[i]) + '/';
	ret += ')';
	return ret;
}
int jump(vector<int>& nums) {
	int n = nums.size();
	vector<int> dp(n+1,INT_MAX);
	dp[0] = 1;
	for (int i = 1; i < n + 1; i++)
	{
		for (int j = i - 1; j >= 0; j--)
		{
			if (nums[j] + j >= i)
				dp[i] = min(dp[i], dp[j] + 1);
		}
	}
	return dp[n];
}
int jump(vector<int>& nums) {
	int n = nums.size(), left = 0, right = 0, maxpos = 0,ret=0;
	while (left <= right)
	{
		if (maxpos >= n - 1)
			return ret;
		for (int i = left;i <= right; i++)
		{
			maxpos = max(maxpos, i + nums[i]);
		}
		left = right + 1;
		right = maxpos;
		ret++;
	}
	return ret;
}
bool canJump(vector<int>& nums) {
	int n = nums.size(), left = 0, right = 0,maxpos=0;
	while (left <= right)
	{
		if (maxpos >= n - 1)
		{
			return true;
		}
		for (int i = left; i <= right; i++)
		{
			maxpos = max(maxpos, nums[i] + i);
		}
		left = right + 1;
		right = maxpos;
	}
	return false;
}
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
	int n = gas.size();
	for (int i = 0; i < n; i++)
	{
		if (gas[i] - cost[i] < 0)
			continue;
		int step = 0;
		for (int rest = 0; step < n; step++)
		{
			int index = (i + step) % n;
			rest += gas[index] - cost[index];
			if (rest < 0)
				break;
		}
		if (step == n)
			return i;
		i += step;
	}
	return -1;
}
int monotoneIncreasingDigits(int n) {
	string s = to_string(n);
	int m = s.size(),i = 0;
	while (i + 1 < n && s[i] < s[i + 1])
		i++;
	if (i + 1 == n - 1)
		return n;
	while (i - 1 >= 0 && s[i] == s[i - 1])
		i--;
	s[i]--;
	for (int j = i + 1; j < m; j++)
		s[j] = '9';
	return stoi(s);
}
int main()
{

	return 0;
}